package 二零年8月;


/**
 * n个筛子的点数
 *
 * 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
 * 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
 *
 * 思路：使用动态规划，  n个筛子抛出的点数总次数和为： 6的n次方，  只要通过dp求出i个骰子掷出s点的次数即可。
 *      dp步骤：（1）定义dp状态： dp[i][s] // 表示i个筛子掷出s点的次数
 *             （2）状态转移方程： dp[i][s]+=dp[i-1][s-j], // 当前n个骰子出现的点数之和等于前一次出现的点数之和加上这一次出现的点数
 *
 * 总结：就是利用dp求出n个筛子所有可能掷出的点数之和情况，然后除以总次数，求得概率。
 */
public class S60 {
    public double[] twoSum(int n) {
        int [][] dp=new int[n+1][6*n+1]; //表示i个骰子掷出s点的次数
        for (int i = 1; i <=6 ; i++) {
            dp[1][i]=1; //表示一个骰子掷出i点的次数为1
        }

        for (int i = 2; i <=n ; i++) {
            for (int s =i; s <=6*i ; s++) { //表示可能出现的点数之和
                for (int j = 1; j <=6 ; j++) { //表示这个骰子能掷出的点数
                    if(s-j<i-1) {//当总数还没有j大时，就不存在这种情况
                        break;
                    }
                    dp[i][s]+=dp[i-1][s-j];
                }
            }
        }
        double total=Math.pow((double) 6,(double)n); //总次数
        double[] ans = new double[5*n+1];//因为最大就只会出现5*n+1中点数
        for(int i=n;i<=6*n;i++){   //因为n个骰子，最小的点数之和是n个1，所以从这个点数开始
            ans[i-n]=((double)dp[n][i])/total;//第i小的点数出现的概率
        }
        return ans;
    }
}
